1. Field of the Invention
The present invention relates to a reversible sequential element and a reversible sequential circuit, and more particularly to a reversible sequential element configured by reversible gates and a reversible sequential circuit configured by the reversible sequential elements.
2. Description of the Related Art
Reversible computing does not result in information loss during the computation process. Thus, it naturally takes care of heating generated due to information loss. Zero energy dissipation would be possible only if the gates in a network are all reversible. As a result, reversibility will become an essential property in future circuit design. Reversible logic has been applied to various future technologies, such as ultra-low-power CMOS design, optical computing, quantum computing and nanotechnology. These technologies increasingly employ reversible logic gates to reduce power computation.
However, the conventional logic gates are almost irreversible. Among the commonly used gates, only NOT gate is reversible. AND gate and OR gate are irreversible because they cannot satisfy the condition of one-to-one and onto mapping between the inputs and outputs of a logic gate. One way to make the AND function reversible is to add one input and two outputs, as shown in FIG. 1(a). These additional input and outputs for reversibility are called garbage bits. The AND function can be obtained in the third output column xy□z (□ representing an XOR gate) of FIG. 1(a), when setting z=0. The truth table of AND function is shown in bold.
This whole truth table is equivalent to the truth table of 3-bit Toffoli gate, and its symbol is shown in FIG. 1(b). The third output column xy□z means that the output is z when x=y=1, and otherwise the output is z. This gate can be used to realize a 2-input reversible AND function by setting z as a constant 0, as mentioned.
Fredkin gate is a reversible gate as well and is also called controlled SWAP gate. FIG. 2(a) is the symbol of Fredkin gate and FIG. 2(b) is its truth table. Its behavior can be described as follows: if the control bit x is set to 1, the outputs of y and z are swapped, otherwise they remain unchanged.
A restriction on reversible logic synthesis has to be followed: the fanout count of a signal net must equal one so that a duplication is necessary if two copies of one signal are needed. This restriction is due to the fact that fanout structure itself is not reversible. For fanout, the number of input signals is one, but there are two or more output signals. Therefore, for this restriction, a 2-bit Toffoli gate is utilized to duplicate a signal. The symbol of a 2-bit Toffoli gate and its truth table are shown in FIGS. 3(a) and 3(b), respectively. The function of the second output column is x□y. If y is set as a constant 0, a copy of input variable x will be obtained in the second output, which is shown in bold. Therefore, the fanout structure in a conventional network can be implemented in this way.
There are two objectives in reversible circuit synthesis:    1. Minimize the number of gates: the number of gates gives a simple estimation of the implementation cost of a reversible circuit.    2. Minimize the number of garbage outputs: we need extra implementation cost (area and power) for those garbage outputs in reversible circuits. Minimizing the number of garbage outputs leads to minimizing the chip area and power consumption of a reversible circuit.
However, the synthesis result of a traditional D latch is not good when the conventional direct transformation method is used to implement a reversible D latch. This is because the D latch is built by many irreversible gates; using the direct transformation method to construct a reversible D latch will require a large number of gates and garbage outputs.